Introduction

Welcome to A* Explorer!

This help file will introduce you to A* Explorer and its various features. What do you want to explore?

Map Features

Maps can be drawn, saved and loaded within A* Explorer. This section will discuss how to perform each of these functions and how to interpret the map's various colours.

Running and Stepping the A* Algorithm

A* Explorer allows the user to either run the A* or step through it incrementally.

Breakpoints and Breaking Conditions

A* Explorer gives the user the opportunity to run the A* until a given point is hit, or a condition is met.

Menu Breakdown

This topic will cover all the menu functions.

Technical Information

Discusses the source code, how to use CAStar and possible improvements to make.


Map Features

This topic will cover A* Explorer's map features.

Drawing Maps

Maps are drawn interactively using the mouse. Simply select the desired weight from the toolbar or menu. Clicking on the map will colour the position in the desired weight.

The darker the colour, the harder it makes the position to transverse with black being impassable. The red and green icons denote the start and end points respectively. You may only have one start point and one end point on any given map.

Important: If an endpoint is placed on a black square, it will render the goal impossible to achieve, since it is not possible to reach the endpoint. If the startpoint is placed on a black square, however, the algorithm will be able to move off the point.

Saving and Loading Maps

Saving and loading maps within A* Explorer is very easy. Once a map has been drawn, select "File, Save" or use the Save icon. Type your filename and hit "Save".

To load your map, select "File, Open", find your map and hit "Open".

Understand the Maps

After running the A* algorithm on a map, your typical map might look something like the shot shown on the right.

As covered, the red and green squares denote the start and end points, and the greyscale boxes are varying weights. The blue square is a node that has been highlighted in the node view (not shown) and the magenta lines show the node's children.

Copyright ©, J.Matthews 2001-2002


Breakpoints

Breakpoints and Break Conditions

A* Explorer has a powerful feature called breakpoints. A breakpoint can either be a specific point or a condition which will cause A* Explorer to stop executing the A*. This is useful if you want to monitor a certain point to see when the A* algorithm uses it, or when (for example) the algorithm must propagate changes backward from a node on the closed list!

Setting a Breakpoint

Setting a breakpoint is very easy, simple double right-click on your map to set a breakpoint. For example, if you double-right click at (8,2) and hit the "Run To Breakpoint" icon, if the A* uses (8,2) this message will appear:

The A* tree view will then jump to (8,2) showing you exactly what has happened. From there, you can run until (8,2) is hit again (Run To Breakpoint), step through the algorithm (Step A*) or complete pathing (Run A*). You may change the position of the breakpoint at any point.

If you want to turn a breakpoint off, select "Pathing, Debug Setup" and deselect ""Breakpoint".

Setting a Break Condition

To set a break condition, simply select the condition you wish from "Pathing, Debug Setup". The conditions are:

Menu Item | Meaning
New Child Added | Triggers when a new child is added.
Open List Added | Triggers when a child that was found on the Open List is added
Closed List Added | Triggers when a child that was found on the Closed List is added
Open List with Update | Triggers when a child that was found on the Open List and updates its parent node is added
Closed List with Update | Triggers when a child that was found on the Closed List and updates its parent node is added

If a condition is met, A* Explorer will display:

Remember, that an entire iteration is performed, therefore it is feasible that the condition occurs several times in one iteration (unlike a breakpoint). Therefore, when a breaking condition is met and the tree view jumps to the node there may be other nodes that satisfy the condition.

Tip: Both a breakpoint and a breaking condition can be specified.


Menu Breakdown

File

New | Creates a new file.
Open | Opens an existing file.
Save | Saves the current map.
Save As | Saves the current map under a different filename.
Exit | Exit A* Explorer.

Pathing

Run A* | Runs the A* Algorithm.
Step A* | Steps the A* algorithm.
Run to Breakpoint | Runs the A* algorithm until a breakpoint or breaking condition is met.
Brush Weight | Opens up a pop-up menu that allows you to specify the weight of the brush.
Debug Setup | Allows you to select/deselect breaking conditions.
Allow Diagonal | Allows the A* to travel diagonally (0,0) to (1,1) for instance.
Relative Costing | Changes the cost function to one that favours relative movement. As in, it favour moving along similar weights rather than the lowest. This is more realistic in certain environments.
Continous Update | Will re-run the A* upon every mouse-click. Note that the A* tree is disabled when this option is set.
Display Goal Node | Will make the A* tree display the goal node.

View

Toolbar | Displays/hides the toolbar
Status Bar | Displays/hides the status bar
A* Route | Displays/hides the route the A* has found. Tip: If you select this while stepping, it will display the current best incomplete route.


Running and Stepping the A* Algorithm

Running the A* Algorithm

If you would just like to find the path between two points, draw your map and select "Pathing, Run A*" or use the icon shown above.

If there is a valid path between the two points, A* Explorer will generate a tree listing all the nodes that have been created along with their f, g, and h-values. The tree uses several types of icons to denote certain node characteristics:

Icon | Meaning
 | Root node
 | A node that was found on the Open List
 | A node that was found on the Closed List
 | A node that was found on the Open List, but the new g-value was better (updated its parent)
 | A node that was found on the Closed List, but the new g-value was better (propagating the changes backwards through the tree)
 | A brand new node

Important: When a node has its parent pointer changed, the tree does not update to reflect that changes.

Stepping the A* Algorithm

A* Explorer allows you to step the algorithm, making sure you can see exactly what is happening.

Once you have drawn your map, select "Pathing, Step A*" or use the icon shown above. When you step the algorithm, several other items in the A* Tree are added. As you can see, the Open and Closed lists are added. Note how the Open list is sorted according to the nodes' f-values.

Every time you hit the step icon (or press F10), the algorithm will make an additional iteration. An iteration counts as selecting the best node, generating the new children and adding them to the Open List.

If you want to run the algorithm continuously from a certain point (or perhaps just see what the Closed and Open lists look like when a path has been found), use the "Run A*" command. If the algorithm has been stepped, it will complete the algorithm until a path has been found, or a path cannot be found.


Technical Information

This section will tell you how to use CAStar. The class is designed to allow it to flexibly adapt to other applications, although the emphasis is on standard tile-based problems. The class uses several function pointers as well as callback data to allow the class to be utilitized in a variety of other ways.

Function Pointers

The function pointers are based around this prototype (defined in ASIncludes.h):

typedef int(*_asFunc)(_asNode *, _asNode *, int, void *);

The two function pointers that are used in the A* algorith are udCost and udValid. udCost will validate the cost of the node. CAStar will pass the parent node, the node in question, the data is always 0, and the void pointer is the m_pCBData member variable. udValid follows the same criteria.

m_pCBData is a void pointer that the programmer can set. It can used to pass a this pointer is static member functions are used in C++ classes.

There are a similar pair of function pointers that can notify an application when an A* event occurs. These are udNotifyChild that is triggered when a child is added. The function passes the parent, then the child, a data item that corresponds to the type of child being added (see ASIncludes.h for the meanings of these values) and then the m_pNCData void pointer. udNotifyList occurs when an item is added or removed from the Open or Closed lists. This passes the previous node in the relevant list, the node in question, a data item (see ASIncludes.h again) and the m_pNCData.

As before, m_pNCData is a void pointer that the programmer can use for his own purposes.

See the A* Explorer source code for specifics/examples on how to use CAStar. Functions to look for include:

CAseDoc::AS_Valid

CAseDoc::AS_Cost

CAseDoc::AS_RelativeCost

CAseDoc::SetupAStar

CNodeView::OnNotifyChild

CNodeView::OnNotifyList

Possible Improvements

  • Add a user-defined function for the heuristic.

  • Template the class for use with other data types?

  • Optimize the algorithm. This was probably require you to remove the notification functions, since they will be a definite source of slow-down.

Hope A* Explorer has helped and feel free to drop me a line at jmatthews@generation5.org for help.